// Growth rate calculator
// Auxiliary data structures used for constructing DFA from a trie
// of forbidden words.

#ifndef LIB_CORE_DFA_CONSTRUCT_H
#define LIB_CORE_DFA_CONSTRUCT_H

#include <string>
#include "grate/dfa.h"

namespace growth_rate {

// All the auxiliary arrays needed by the DFA construction algorithm
// are bit-packed as dense as possible, and are stored as array of bytes.
// For each node we store:
//   lf: lexmin failure function (size: log(DFA_size) bits)
//   last: maximal letter on path from root to node
//         (size: log(alphabet_size + 1) bits)
//   sigma: permutation of letters to use to transform current word to
//          a word corresponding to lf
//          (size: log(alphabet_size + 1) * alphabet_size bits).
//   back: mask that states which outgoing edges lead up the trie
//          (size: alphabet_size bits).
class NodeData {
 public:
  explicit NodeData(const DFAInterface *dfa);
  ~NodeData();

  size_t get_lf(size_t node) const;
  uint8_t get_last(size_t node) const;
  uint8_t get_sigma(size_t node, uint8_t letter) const;
  bool get_back(size_t node, uint8_t letter) const;
  void set_lf(size_t node, size_t lf);
  void set_last(size_t node, uint8_t last);
  void set_sigma(size_t node, uint8_t letter, uint8_t sigma);
  void set_back(size_t node, uint8_t letter, bool back);
  // Dump all the data for a given node in a human-readable format.
  std::string dump_node(size_t node) const;

  void copy_sigma(size_t dest_node, size_t src_node);
  void copy_sigma_to_array(size_t node, uint8_t *array);
  void apply_to_sigma(size_t node, uint8_t *permut);

  // Marks "undefined" value for letter (used in array "sigma".
  uint8_t undefined_letter() const { return dfa_->alphabet_size(); }
  size_t node_size_in_bits() const { return node_size_in_bits_; }
  size_t data_size_in_bytes() const { return data_size_in_bytes_; }

 private:
  const DFAInterface *dfa_;
  const size_t lf_size_;
  const size_t letter_size_;  // bits to encode a single letter (or undef value)
  const size_t last_size_;
  const size_t sigma_size_;
  const size_t back_size_;
  const size_t node_size_in_bits_;
  const size_t data_size_in_bytes_;

  // Array of bytes containing packed lf, last, sigma and back for
  // each node.
  uint8_t *data_;
};

// NodeQueue is used by the construction procedure to traverse trie
// nodes in the order of BFS.
class NodeQueue {
 public:
  explicit NodeQueue(size_t size);
  ~NodeQueue();
  bool push(size_t node);  // Returns false if the queue is full already.
  size_t pop();
  bool empty() const;
 private:
  const size_t size_;
  size_t head_index_;  // number of first element. Lies in [0, size_).
  size_t tail_index_;  // index of element after last. Lies in [0, size_).
  size_t *queue_;  // data
};

}  // namespace growth_rate

#endif  // LIB_CORE_DFA_CONSTRUCT_H
